namespace Test.ConsoleProgram.Algorithm.Solution
{
    [TestDescription("算法: 0392. 判断子序列")]
    public class No0392_IsSubsequence : AbsBaseTestItem
    {
        /*
        给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
        你可以认为 s 和 t 中仅包含英文小写字母。
        字符串 t 可能会很长（长度 ~= 500,000），而 s 是个短字符串（长度 <=100）。
        字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。
        （例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

        后续挑战 :
            如果有大量输入的 S，称作S1, S2, ... , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？
        */

        public override void OnTest()
        {
            Assert.TestExe(IsSubsequence, "ace", "abcde", true);
            Assert.TestExe(IsSubsequence, "aec", "abcde", false);
            Assert.TestExe(IsSubsequence, "acb", "ahbgdc", false);
            Assert.TestExe(IsSubsequence, "abc", "ahbgdc", true);
            Assert.TestExe(IsSubsequence, "axc", "ahbgdc", false);
        }

        /// <summary>
        /// 方法一：双指针
        /// </summary>
        public bool IsSubsequence(string s, string t)
        {
            int sn = s.Length, tn = t.Length;
            int si = 0, ti = 0;
            while (si < sn && ti < tn)
            {
                if (s[si] == t[ti])
                {
                    si++;
                }
                ti++;
            }
            return si == sn;
        }
    }
}
